package com.lft.tree10.segment_tree2;

/**
 * 线段树
 */
public class SegmentTreeDemo {
	public static void main(String[] args) {
		Integer[] a = {3, 5, 6, 8, 4, 2, 1, 7, 9};
	}
}

class SegmentTree {
	private Node root;
	
	/**
	 * 构造器
	 * @param arr    原始数组
	 * @param merger 自己实现的合并方法
	 */
	public SegmentTree(int left, int right) {
		// 构建线段树
		root = buildSegment(left, right);
	}
	
	private Node buildSegment(int left, int right) {
		Node node = new Node(left, right);
		if (right - left >= 1) {
			int mid = (left + right) / 2;
			node.leftChild = buildSegment(left, mid);
			node.rightChild = buildSegment(mid + 1, right);
		}
		return node;
	}
	
	/**
	 * 查询线段树——递归实现
	 * @param left  查询的左边界
	 * @param right 查询的右边界
	 * @return
	 */
	public int query(int left, int right) {
		return query(root, left, right);
	}
	
	/**
	 * 查询线段树——递归实现
	 * @param rootNode
	 * @param leftIndex  查询的左边界
	 * @param rightIndex 查询的右边界
	 * @return
	 */
	private int query(Node rootNode, int leftIndex, int rightIndex) {
		if (leftIndex > rightIndex) {
			return 0;
		}
		if (rootNode.leftIndex == leftIndex && rootNode.rightIndex == rightIndex) {
			return rootNode.val;
		}
		int mid = (leftIndex + rightIndex) / 2;
		return query(rootNode.leftChild, leftIndex, mid) + query(rootNode.rightChild, mid + 1, rightIndex);
		
	}
	
	/**
	 * 更新线段树的某一节点的值——递归实现
	 * @param index    要更新的节点的索引
	 * @param newValue 新值
	 * @return 修改之前的值。
	 */
	public void updateOne(int index, int newValue) {
		if (index < 0) {
			throw new IllegalArgumentException("Index Out Of Bounds");
		}
		updateOne(root, index, newValue);
	}
	
	/**
	 * 更新线段树的某一节点的值——递归实现
	 * 顺带更新父节点的值
	 */
	private int updateOne(Node node, int index, int newValue) {
		// 左边界索引和查询的左边界相等，右边界索引和查询的右边界相等。当前树节点索引就是要查找的。
		if (node.leftIndex == node.rightIndex && node.leftIndex == index) {
			int tempValue = node.val;
			node.val = newValue;
			return node.val;
		} else {
			int mid = (node.leftIndex + node.rightIndex) / 2;
			if (index <= mid) {
				node.val = node.rightChild.val + updateOne(node.leftChild, index, newValue);
			} else {
				node.val = node.leftChild.val + updateOne(node.rightChild, index, newValue);
			}
			return node.val;
		}
	}
}

class Node implements Comparable<Node> {
	int val;
	int leftIndex;
	int rightIndex;
	Node leftChild;
	Node rightChild;
	
	public Node(int leftIndex, int rightIndex) {
		this.val = 0;
		this.leftIndex = leftIndex;
		this.rightIndex = rightIndex;
		this.leftChild = null;
		this.rightChild = null;
	}
	
	@Override
	public int compareTo(Node o) {
		return this.val - o.val;
	}
}
